package com.github.hgkmail.hello.leetcode101.top100;

//2次分类讨论，先按位(千 百 十 个)讨论，再按范围(9 8~5 4 3~1)讨论。
public class LC12IntegerToRoman {
    public void appendMulti(StringBuilder sb, String s, int n) {
        for (int i = 0; i < n; i++) {
            sb.append(s);
        }
    }

    /**
     * 按范围讨论(9 8~5 4 3~1)
     * @param sb
     * @param n
     * @param one 一的表示
     * @param five 五的表示
     * @param ten 十的表示
     */
    public void appendDigit(StringBuilder sb, int n, String one, String five, String ten) {
        if (n==9) {
            sb.append(one).append(ten);
        } else if (n<9 && n>=5) {
            sb.append(five);
            appendMulti(sb, one, n-5);
        } else if (n==4) {
            sb.append(one).append(five);
        } else {
            appendMulti(sb, one, n);
        }
    }

    //1 <= num <= 3999
    //按位讨论(千 百 十 个)
    public String intToRoman(int num) {
        if (num<=0) {
            return "";
        }
        String str = String.valueOf(num);
        int len=str.length();
        StringBuilder sb = new StringBuilder();
        int index=0, n=0;
        //千位
        if (len==4) {
            n = Integer.parseInt(str.substring(index, index+1));
            appendMulti(sb, "M", n);
            index++;
        }
        //百位、十位、个位
        String[][] config = new String[][]{{"I","V","X"},{"X","L","C"},{"C","D","M"}};
        for (int i = 3; i >=1 ; i--) {
            if (len>=i) {
                n = Integer.parseInt(str.substring(index, index+1));
                if (n>0) {
                    appendDigit(sb, n, config[i-1][0], config[i-1][1], config[i-1][2]);
                }
                index++;
            }
        }
        return sb.toString();
    }

    //符号表法
    public String intToRoman2(int num) {
        //穷举所有可能的组合，降序排列
        int[] values=new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols=new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num>=values[i]) { //能减成功，就append符号
                num-=values[i];
                sb.append(symbols[i]);
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new LC12IntegerToRoman().intToRoman2(1994));
        System.out.println(new LC12IntegerToRoman().intToRoman2(58));
        System.out.println(new LC12IntegerToRoman().intToRoman2(9));
    }
}
